package com.snopy.leetcode.index1_1000.index701_800;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Question821
 * @description 字符的最短距离
 *
 * 给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
 *
 * 返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
 *
 * 两个下标i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。
 *
 * 示例 1：
 *
 * 输入：s = "loveleetcode", c = "e"
 * 输出：[3,2,1,0,1,0,0,1,2,2,1,0]
 * 解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
 * 距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
 * 距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
 * 对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
 * 距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。
 * 示例 2：
 *
 * 输入：s = "aaab", c = "b"
 * 输出：[3,2,1,0]
 *
 * @email 77912204@qq.com
 * @date 2022/04/19 18:35
 */
public class Question821 {
    public static void main(String[] args) {
        String str = "loveleetcode";
        char c = 'e';
        int[] nums = shortestToChar(str, c);
        for (int num : nums) {
            System.out.print(num+"\t");
        }
    }
    /**
     * @Description 2次遍历，第一次出距离左边目标的距离，第二次找出距离右边目标的距离，并比较两次的距离，那个比较小
     * @param s:
     * @param c:
     * @return: int[]
     * @Date 2022-04-19
     * @Author txl77912204@gmail.com
     **/
    public static int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] nums = new int[n];
        for (int i = 0,idx = -n; i < n; i++) {
            if (s.charAt(i) == c){
                idx = i;
            }
            nums[i] = i - idx;
        }
        for (int num : nums) {
            System.out.print(num+"\t");
        }
        System.out.println();
        for (int i = n-1,idx = 2*n;i>=0;i--){
            if (s.charAt(i) == c){
                idx = i;
            }
            nums[i] = Math.min(nums[i],idx-i);
        }
        return nums;
    }
}
